{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Meeting Scheduler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAvailableDuration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #安排会议日程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个人的空闲时间表：<code>slots1</code> 和 <code>slots2</code>，以及会议的预计持续时间&nbsp;<code>duration</code>，请你为他们安排&nbsp;<strong>时间段最早&nbsp;且</strong>合适的会议时间。</p>\n",
    "\n",
    "<p>如果没有满足要求的会议时间，就请返回一个 <strong>空数组</strong>。</p>\n",
    "\n",
    "<p>「空闲时间」的格式是&nbsp;<code>[start, end]</code>，由开始时间&nbsp;<code>start</code>&nbsp;和结束时间&nbsp;<code>end</code>&nbsp;组成，表示从&nbsp;<code>start</code>&nbsp;开始，到 <code>end</code>&nbsp;结束。&nbsp;</p>\n",
    "\n",
    "<p>题目保证数据有效：同一个人的空闲时间不会出现交叠的情况，也就是说，对于同一个人的两个空闲时间&nbsp;<code>[start1, end1]</code>&nbsp;和&nbsp;<code>[start2, end2]</code>，要么&nbsp;<code>start1 &gt; end2</code>，要么&nbsp;<code>start2 &gt; end1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8\n",
    "<strong>输出：</strong>[60,68]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= slots1.length, slots2.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>slots1[i].length, slots2[i].length == 2</code></li>\n",
    "\t<li><code>slots1[i][0] &lt; slots1[i][1]</code></li>\n",
    "\t<li><code>slots2[i][0] &lt; slots2[i][1]</code></li>\n",
    "\t<li><code>0 &lt;= slots1[i][j], slots2[i][j] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= duration &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [meeting-scheduler](https://leetcode.cn/problems/meeting-scheduler/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [meeting-scheduler](https://leetcode.cn/problems/meeting-scheduler/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[10,50],[60,120],[140,210]]\\n[[0,15],[60,70]]\\n8', '[[10,50],[60,120],[140,210]]\\n[[0,15],[60,70]]\\n12']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "\n",
    "        left_1 = 0\n",
    "        left_2 = 0\n",
    "\n",
    "        while left_1 < len(slots1) and left_2 < len(slots2):\n",
    "            slot_1 = slots1[left_1]\n",
    "            slot_2 = slots2[left_2]\n",
    "\n",
    "            start = max(slot_1[0],slot_2[0])\n",
    "            end = min(slot_1[1],slot_2[1])\n",
    "\n",
    "            if end - start >= duration:\n",
    "                return [start, start+duration]\n",
    "            \n",
    "            if slot_1[1] < slot_2[1]:\n",
    "                left_1+=1\n",
    "            else:\n",
    "                left_2 +=1\n",
    "\n",
    "        \n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        m, n = len(slots1), len(slots2)\n",
    "        i = j = 0\n",
    "        while i<m and j < n:\n",
    "            x, y = slots1[i]\n",
    "            a, b = slots2[j]\n",
    "            if y <= a or b <= x:\n",
    "                if y<=a:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            else:\n",
    "                low= a if a > x else x\n",
    "                high = b if b < y else y\n",
    "                if high-low>=duration:\n",
    "                    return [low, low+duration]\n",
    "                if y<b:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "\n",
    "        left_1 = 0\n",
    "        left_2 = 0\n",
    "\n",
    "        while left_1 < len(slots1) and left_2 < len(slots2):\n",
    "            slot_1 = slots1[left_1]\n",
    "            slot_2 = slots2[left_2]\n",
    "\n",
    "            start = max(slot_1[0],slot_2[0])\n",
    "            end = min(slot_1[1],slot_2[1])\n",
    "\n",
    "            if end - start >= duration:\n",
    "                return [start, start+duration]\n",
    "            \n",
    "            if slot_1[1] < slot_2[1]:\n",
    "                left_1+=1\n",
    "            else:\n",
    "                left_2 +=1\n",
    "\n",
    "        \n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        pointer1 = pointer2 = 0\n",
    "\n",
    "        while pointer1 < len(slots1) and pointer2 < len(slots2):\n",
    "            # 找出交集的边界，或者通用的时间段\n",
    "            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])\n",
    "            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])\n",
    "            if intersect_right - intersect_left >= duration:\n",
    "                return [intersect_left, intersect_left + duration]\n",
    "            # 始终移动那个结束时间较早的时间段\n",
    "            if slots1[pointer1][1]< slots2[pointer2][1]:\n",
    "                pointer1 += 1\n",
    "            else:\n",
    "                pointer2 += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        pointer1 = pointer2 = 0\n",
    "\n",
    "        while pointer1 < len(slots1) and pointer2 < len(slots2):\n",
    "            # 找出交集的边界，或者通用的时间段\n",
    "            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])\n",
    "            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])\n",
    "            if intersect_right - intersect_left >= duration:\n",
    "                return [intersect_left, intersect_left + duration]\n",
    "            # 始终移动那个结束时间较早的时间段\n",
    "            if slots1[pointer1][1]< slots2[pointer2][1]:\n",
    "                pointer1 += 1\n",
    "            else:\n",
    "                pointer2 += 1\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 双指针\n",
    "    def minAvailableDuration1(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        pointer1 = pointer2 = 0\n",
    "\n",
    "        while pointer1 < len(slots1) and pointer2 < len(slots2):\n",
    "            # 找出交集的边界，或者通用的时间段\n",
    "            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])\n",
    "            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])\n",
    "            if intersect_right - intersect_left >= duration:\n",
    "                return [intersect_left, intersect_left + duration]\n",
    "\n",
    "            # 始终移动那个结束时间较早的时间段\n",
    "            if slots1[pointer1][1]< slots2[pointer2][1]:\n",
    "                pointer1 += 1\n",
    "            else:\n",
    "                pointer2 += 1\n",
    "\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "    # 堆\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        # 构建一个包含持续时间长于持续时间的时隙的堆\n",
    "        timeslots = list(filter(lambda x: x[1] - x[0] >= duration, slots1 + slots2))\n",
    "        heapq.heapify(timeslots)\n",
    "\n",
    "        while len(timeslots) > 1:\n",
    "            start1, end1 = heapq.heappop(timeslots)\n",
    "            start2, end2 = timeslots[0]\n",
    "            if end1 >= start2 + duration:\n",
    "                return [start2, start2 + duration]\n",
    "\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        # 双指针\n",
    "        m, n = 0, 0\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        \n",
    "        while m < len(slots1) and n < len(slots2):\n",
    "            print(m, n)\n",
    "            # 如果其中一个结束时间小于另一个开始时间，即没有重叠区域\n",
    "            if slots1[m][1] <= slots2[n][0]:\n",
    "                m += 1\n",
    "            elif slots2[n][1] <= slots1[m][0]:\n",
    "                n += 1\n",
    "            else:\n",
    "                left = max(slots1[m][0], slots2[n][0])\n",
    "                right = min(slots1[m][1], slots2[n][1])\n",
    "                if right - left >= duration:\n",
    "                    return [left, left + duration]\n",
    "                else:\n",
    "                    if slots1[m][1] < slots2[n][1]:\n",
    "                        m += 1\n",
    "                    else:\n",
    "                        n += 1\n",
    "\n",
    "\n",
    "\n",
    "        return []\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 双指针\n",
    "    def minAvailableDuration1(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        pointer1 = pointer2 = 0\n",
    "\n",
    "        while pointer1 < len(slots1) and pointer2 < len(slots2):\n",
    "            # 找出交集的边界，或者通用的时间段\n",
    "            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])\n",
    "            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])\n",
    "            if intersect_right - intersect_left >= duration:\n",
    "                return [intersect_left, intersect_left + duration]\n",
    "\n",
    "            # 始终移动那个结束时间较早的时间段\n",
    "            if slots1[pointer1][1]< slots2[pointer2][1]:\n",
    "                pointer1 += 1\n",
    "            else:\n",
    "                pointer2 += 1\n",
    "\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "    # 堆\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        # 构建一个包含持续时间长于持续时间的时隙的堆\n",
    "        timeslots = list(filter(lambda x: x[1] - x[0] >= duration, slots1 + slots2))\n",
    "        # print(slots1 + slots2)\n",
    "\n",
    "        heapq.heapify(timeslots)\n",
    "\n",
    "        while len(timeslots) > 1:\n",
    "            start1, end1 = heapq.heappop(timeslots)\n",
    "            start2, end2 = timeslots[0]\n",
    "            if end1 >= start2 + duration:\n",
    "                return [start2, start2 + duration]\n",
    "\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        def getIntersection(slot1: list, slot2: list) -> (int, int):\n",
    "            return max(slot1[0], slot2[0]), min(slot1[1], slot2[1])\n",
    "\n",
    "        slots1, slots2 = sorted(slots1), sorted(slots2)\n",
    "        p1, p2 = 0, 0\n",
    "\n",
    "        while p1 < len(slots1) and p2 < len(slots2):\n",
    "            left, right = getIntersection(slots1[p1], slots2[p2])\n",
    "            if right - left >= duration: return [left, left + duration]\n",
    "            else:\n",
    "                if slots1[p1][1] <= slots2[p2][1]:\n",
    "                    p1 += 1\n",
    "                else:\n",
    "                    p2 += 1\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        d = duration\n",
    "        ts = [(s,e) for s, e in slots1 + slots2 if e - s >= d]\n",
    "        heapq.heapify(ts)\n",
    "        while len(ts) > 1:\n",
    "            s1, e1 = heapq.heappop(ts)\n",
    "            s2, e2 = ts[0]\n",
    "            if e1 >= s2 + d:\n",
    "                return [s2, s2 + d]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        timeslots=list(filter(lambda x: x[1]-x[0]>=duration, slots1+slots2))\n",
    "        heapq.heapify(timeslots)\n",
    "\n",
    "        while len(timeslots)>1:\n",
    "            start1, end1 = heapq.heappop(timeslots)\n",
    "            start2, end2 = timeslots[0]\n",
    "            if end1>=start2+duration:\n",
    "                return [start2, start2+duration]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        n1, n2 = len(slots1), len(slots2)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < n1 and j < n2:\n",
    "            s1, e1 = slots1[i]\n",
    "            s2, e2 = slots2[j]\n",
    "            s = max(s1, s2)\n",
    "            e = min(e1, e2)\n",
    "            if e - s >= duration:\n",
    "                return [s, s + duration]\n",
    "            if e1 < e2:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        arr = [(s, e) for s, e in slots1 if (e - s) >= duration]\n",
    "        brr = [(s, e) for s, e in slots2 if (e - s) >= duration]\n",
    "        arr.sort() \n",
    "        arr = [(float('-inf'), float('-inf'))] + arr + [(float('inf'), float('inf'))] \n",
    "        brr.sort() \n",
    "        def upper_bound(x):\n",
    "            l, r = -1, len(arr)\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if arr[mid][0] <= x:\n",
    "                    l = mid \n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return l \n",
    "        #print(arr)\n",
    "        #print(brr) \n",
    "        for s, e in brr:\n",
    "            idx1 = upper_bound(s)\n",
    "            idx2 = upper_bound(e) \n",
    "            #print(idx1, idx2) \n",
    "            for i in range(idx1, idx2+1):\n",
    "                if arr[i][0] <= s <= arr[i][1] and e >= arr[i][1] and arr[i][1] - s >= duration:\n",
    "                    return [s, s+duration] \n",
    "                if s <= arr[i][0] and e >= arr[i][1]:\n",
    "                    return [arr[i][0], arr[i][0] + duration]\n",
    "                if s <= arr[i][0] and arr[i][0] <= e <= arr[i][1] and e - arr[i][0] >= duration:\n",
    "                    return [arr[i][0], arr[i][0] + duration]\n",
    "                if arr[i][0] <= s and e <= arr[i][1]:\n",
    "                    return [s, s+duration] \n",
    "        return [] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        # 双指针\n",
    "        m, n = 0, 0\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        \n",
    "        while m < len(slots1) and n < len(slots2):\n",
    "            # 如果其中一个结束时间小于另一个开始时间，即没有重叠区域\n",
    "            if slots1[m][1] <= slots2[n][0]:\n",
    "                m += 1\n",
    "            elif slots2[n][1] <= slots1[m][0]:\n",
    "                n += 1\n",
    "            else:\n",
    "                left = max(slots1[m][0], slots2[n][0])\n",
    "                right = min(slots1[m][1], slots2[n][1])\n",
    "                if right - left >= duration:\n",
    "                    return [left, left + duration]\n",
    "                else:\n",
    "                    if slots1[m][1] < slots2[n][1]:\n",
    "                        m += 1\n",
    "                    else:\n",
    "                        n += 1\n",
    "\n",
    "\n",
    "\n",
    "        return []\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        def getIntersection(slot1: list, slot2: list) -> (int, int):\n",
    "            return max(slot1[0], slot2[0]), min(slot1[1], slot2[1])\n",
    "\n",
    "        slots1, slots2 = sorted(slots1), sorted(slots2)\n",
    "        p1, p2 = 0, 0\n",
    "\n",
    "        while p1 < len(slots1) and p2 < len(slots2):\n",
    "            left, right = getIntersection(slots1[p1], slots2[p2])\n",
    "            if right - left >= duration: return [left, left + duration]\n",
    "            else:\n",
    "                if slots1[p1][1] <= slots2[p2][1]:\n",
    "                    p1 += 1\n",
    "                else:\n",
    "                    p2 += 1\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        m, n = len(slots1), len(slots2)\n",
    "        queue = []\n",
    "        heapq.heappush(queue, [slots1[0][1], slots1[0][0], 0])\n",
    "        heapq.heappush(queue, [slots2[0][1], slots2[0][0], -1])\n",
    "        while len(queue) == 2:\n",
    "            end, start, index = heapq.heappop(queue)\n",
    "            if min(end, queue[0][0]) - max(start, queue[0][1]) >= duration:\n",
    "                start = max(start, queue[0][1])\n",
    "                return [start, start+duration]\n",
    "            if index >= 0 and index + 1 < m:\n",
    "                index += 1\n",
    "                heapq.heappush(queue, [slots1[index][1], slots1[index][0], index])\n",
    "            elif index < 0 and index - 1 >= -n:\n",
    "                index -= 1\n",
    "                heapq.heappush(queue, [slots2[-index-1][1], slots2[-index-1][0], index])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        m = len(slots1)\n",
    "        n = len(slots2)\n",
    "        i = j = 0\n",
    "        while i < m and j < n:\n",
    "            lower = max(slots1[i][0], slots2[j][0])\n",
    "            upper = min(slots1[i][1], slots2[j][1])\n",
    "            d = upper - lower\n",
    "            if d >= duration:\n",
    "                return [lower, lower+duration]\n",
    "            if slots1[i][1] > slots2[j][1]:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        # 两个空闲时间的重叠时间为min(slots1[i][1], slots2[i][1]) - max(slots1[i][0], slots2[i][0])\n",
    "        slots1.sort(key=lambda x:x[0])\n",
    "        slots2.sort(key=lambda x:x[0])\n",
    "        i, j = 0, 0\n",
    "        while i < len(slots1) and j < len(slots2):\n",
    "            if min(slots1[i][1], slots2[j][1]) - max(slots1[i][0], slots2[j][0]) < duration:\n",
    "                if i == len(slots1) - 1 and j < len(slots2) - 1:\n",
    "                    j += 1\n",
    "                elif j == len(slots2) - 1 and i < len(slots1) - 1:\n",
    "                    i += 1\n",
    "                elif i == len(slots1) - 1 and j == len(slots2) - 1:\n",
    "                    return []\n",
    "                else:\n",
    "                    if slots1[i+1][0] <= slots2[j+1][0]:\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        j += 1\n",
    "            else:\n",
    "                return [max(slots1[i][0], slots2[j][0]), max(slots1[i][0], slots2[j][0]) + duration]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        # 双指针\n",
    "        s1, s2 = 0, 0\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        \n",
    "        while s1 < len(slots1) and s2 < len(slots2):\n",
    "            # 判断谁先开始\n",
    "            left = max(slots1[s1][0], slots2[s2][0])\n",
    "            right = min(slots1[s1][1], slots2[s2][1])\n",
    "            if right - left >= duration:\n",
    "                return [left , left + duration]\n",
    "            else:\n",
    "                # 移动先结束的那个\n",
    "                if slots1[s1][1] < slots2[s2][1]:\n",
    "                    s1 += 1\n",
    "                else:\n",
    "                    s2 += 1\n",
    "\n",
    "\n",
    "        return []\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        i = j = 0\n",
    "        m,n = len(slots1),len(slots2)\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        while i < m and j < n:\n",
    "            left = max(slots1[i][0],slots2[j][0])\n",
    "            right = min(slots1[i][1], slots2[j][1])\n",
    "            if right - left >= duration:\n",
    "                return [left,left + duration]\n",
    "            if slots1[i][1] < slots2[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        pointer1 = pointer2 = 0\n",
    "\n",
    "        while pointer1 < len(slots1) and pointer2 < len(slots2):\n",
    "            # 找出交集的边界，或者通用的时间段\n",
    "            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])\n",
    "            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])\n",
    "            if intersect_right - intersect_left >= duration:\n",
    "                return [intersect_left, intersect_left + duration]\n",
    "            # 始终移动那个结束时间较早的时间段\n",
    "            if slots1[pointer1][1]< slots2[pointer2][1]:\n",
    "                pointer1 += 1\n",
    "            else:\n",
    "                pointer2 += 1\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        n1, n2 = len(slots1), len(slots2)\n",
    "\n",
    "        l1, l2, ans = 0, 0, []\n",
    "        while l1<n1 and l2<n2:\n",
    "            left=max(slots1[l1][0], slots2[l2][0])\n",
    "            right=min(slots1[l1][1], slots2[l2][1])\n",
    "\n",
    "            if right-left>=duration:\n",
    "\n",
    "                ans.append(left)\n",
    "                ans.append(left+duration)\n",
    "                return ans # 【关键】！\n",
    "            \n",
    "            #elif slots1[l1][1]<slots2[l2][1]:\n",
    "            if slots1[l1][1]<slots2[l2][1]: # 【关键】：不是elif！\n",
    "                l1+=1\n",
    "\n",
    "            else:\n",
    "                l2+=1\n",
    "        \n",
    "        return ans #【关键】：ans=[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        # 双指针\n",
    "        m, n = 0, 0\n",
    "        slots1 = sorted(slots1, key = lambda x:x[0])\n",
    "        slots2.sort()\n",
    "        \n",
    "        while m < len(slots1) and n < len(slots2):\n",
    "            # 如果其中一个结束时间小于另一个开始时间，即没有重叠区域\n",
    "            if slots1[m][1] <= slots2[n][0]:\n",
    "                m += 1\n",
    "            elif slots2[n][1] <= slots1[m][0]:\n",
    "                n += 1\n",
    "            else:\n",
    "                # 如果有重叠，取出重叠的左右边界，判断是否足够放下一次会议\n",
    "                left = max(slots1[m][0], slots2[n][0])\n",
    "                right = min(slots1[m][1], slots2[n][1])\n",
    "                if right - left >= duration:\n",
    "                    return [left, left + duration]\n",
    "                else:\n",
    "                    # 如果不够，让先结束的那个（注意不是先开始的那个）往前进一个\n",
    "                    if slots1[m][1] < slots2[n][1]:\n",
    "                        m += 1\n",
    "                    else:\n",
    "                        n += 1\n",
    "\n",
    "\n",
    "\n",
    "        return []\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        #========= ========== =======\n",
    "        #      ************ ************\n",
    "        slots1 = [(s,e) for s, e in slots1 if e - s >= duration]\n",
    "        slots2 = [(s,e) for s, e in slots2 if e - s >= duration]\n",
    "        slots1.sort(key=lambda x: x[0])\n",
    "        slots2.sort(key=lambda x: x[0])\n",
    "        for s1, e1 in slots1:\n",
    "            for s2, e2 in slots2:\n",
    "                if s2 <= s1 and e2 - duration >= s1:\n",
    "                    return [s1, s1 + duration]\n",
    "                if s2 > s1 and s2 + duration <= e1:\n",
    "                    return [s2, s2 + duration]\n",
    "        return []\n",
    "        # 6  8 10 -> 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        i, j = 0, 0\n",
    "        # we need to find an intersect\n",
    "        def overlap(blk2, blk1):  # returns int\n",
    "            s1, e1 = blk1\n",
    "            s2, e2 = blk2\n",
    "            if e1 < s2 or e2 < s1:\n",
    "                return 0\n",
    "            return min(e2, e1) - max(s1, s2)\n",
    "        \n",
    "        #\n",
    "        # print(overlap([0,3], [2,3]))\n",
    "        # print(overlap([0,3], [1,4]))\n",
    "        # print(overlap([0,3], [3,4]))\n",
    "        slots1.sort(), slots2.sort()\n",
    "        n1 = len(slots1)\n",
    "        n2 = len(slots2)\n",
    "        c = - (1 << 30)\n",
    "        while c < 500 and i < n1 or j < n2:  # how is this overpassing\n",
    "            # print(i, \" \", j)\n",
    "            c += 1\n",
    "            o = overlap(slots1[min(n1 - 1, i)], slots2[min(n2-1, j)])\n",
    "            if o >= duration:\n",
    "                start = max(slots1[i][0], slots2[j][0])\n",
    "                return [start, start + duration]\n",
    "            else:\n",
    "                if i > n1 - 1:\n",
    "                    j += 1\n",
    "                elif j > n2 - 1:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    if slots1[min(n1-1, i)][1] > slots2[min(n2-1, j)][1]:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        i += 1\n",
    "\n",
    "        return []\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort(key=lambda x:x[0])\n",
    "        slots2.sort(key=lambda x:x[0])\n",
    "        i, j = 0, 0\n",
    "        while i < len(slots1) and j < len(slots2):\n",
    "            if min(slots1[i][1], slots2[j][1]) - max(slots1[i][0], slots2[j][0]) < duration:\n",
    "                if i == len(slots1) - 1 and j < len(slots2) - 1:\n",
    "                    j += 1\n",
    "                elif i < len(slots1) - 1 and j == len(slots2) - 1:\n",
    "                    i += 1\n",
    "                elif i == len(slots1) - 1 and j == len(slots2) - 1:\n",
    "                    return []\n",
    "                else:\n",
    "                    if slots1[i+1][0] <= slots2[j+1][0]:\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        j += 1\n",
    "            else:\n",
    "                return [max(slots1[i][0], slots2[j][0]), max(slots1[i][0], slots2[j][0])+duration]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        p1, p2 = 0, 0\n",
    "        while p1 < len(slots1) and p2 < len(slots2):\n",
    "            left = max(slots1[p1][0], slots2[p2][0])\n",
    "            right = min(slots1[p1][1], slots2[p2][1])\n",
    "            if right - left >= duration:\n",
    "                return [left, left+duration]\n",
    "            if slots1[p1][1] < slots2[p2][1]:\n",
    "                p1 += 1\n",
    "            else:\n",
    "                p2 += 1\n",
    "        return list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        m, n = len(slots1), len(slots2)\n",
    "        queue = []\n",
    "        heapq.heappush(queue, [slots1[0][1], slots1[0][0], 0])\n",
    "        heapq.heappush(queue, [slots2[0][1], slots2[0][0], -1])\n",
    "        while len(queue) == 2:\n",
    "            end, start, index = heapq.heappop(queue)\n",
    "            if min(end, queue[0][0]) - max(start, queue[0][1]) >= duration:\n",
    "                start = max(start, queue[0][1])\n",
    "                return [start, start+duration]\n",
    "            if index >= 0 and index + 1 < m:\n",
    "                index += 1\n",
    "                heapq.heappush(queue, [slots1[index][1], slots1[index][0], index])\n",
    "            elif index < 0 and index - 1 >= -n:\n",
    "                index -= 1\n",
    "                heapq.heappush(queue, [slots2[-index-1][1], slots2[-index-1][0], index])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 双指针\n",
    "    def minAvailableDuration1(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        pointer1 = pointer2 = 0\n",
    "\n",
    "        while pointer1 < len(slots1) and pointer2 < len(slots2):\n",
    "            # 找出交集的边界，或者通用的时间段\n",
    "            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])\n",
    "            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])\n",
    "            if intersect_right - intersect_left >= duration:\n",
    "                return [intersect_left, intersect_left + duration]\n",
    "\n",
    "            # 始终移动那个结束时间较早的时间段\n",
    "            if slots1[pointer1][1]< slots2[pointer2][1]:\n",
    "                pointer1 += 1\n",
    "            else:\n",
    "                pointer2 += 1\n",
    "\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "    # 堆\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        pointer1 = pointer2 = 0\n",
    "\n",
    "        while pointer1 < len(slots1) and pointer2 < len(slots2):\n",
    "            # 找出交集的边界，或者通用的时间段\n",
    "            intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])\n",
    "            intersect_left = max(slots1[pointer1][0],slots2[pointer2][0])\n",
    "            if intersect_right - intersect_left >= duration:\n",
    "                return [intersect_left, intersect_left + duration]\n",
    "                \n",
    "            # 始终移动那个结束时间较早的时间段\n",
    "            if slots1[pointer1][1]< slots2[pointer2][1]:\n",
    "                pointer1 += 1\n",
    "            else:\n",
    "                pointer2 += 1\n",
    "\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        i, j = 0, 0\n",
    "        m, n = len(slots1), len(slots2)\n",
    "        while i < m and j < n:\n",
    "            left =  max(slots1[i][0], slots2[j][0])\n",
    "            right =  min(slots1[i][1], slots2[j][1])\n",
    "            if right - left >= duration:\n",
    "                return [left, left + duration]\n",
    "            if slots1[i][1] < slots2[j][1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort()\n",
    "        slots2.sort()\n",
    "        m, n = len(slots1), len(slots2)\n",
    "        queue = []\n",
    "        heapq.heappush(queue, [slots1[0][1], slots1[0][0], 0])\n",
    "        heapq.heappush(queue, [slots2[0][1], slots2[0][0], -1])\n",
    "        while len(queue) == 2:\n",
    "            end, start, index = heapq.heappop(queue)\n",
    "            if min(end, queue[0][0]) - max(start, queue[0][1]) >= duration:\n",
    "                start = max(start, queue[0][1])\n",
    "                return [start, start+duration]\n",
    "            if index >= 0 and index + 1 < m:\n",
    "                index += 1\n",
    "                heapq.heappush(queue, [slots1[index][1], slots1[index][0], index])\n",
    "            elif index < 0 and index - 1 >= -n:\n",
    "                index -= 1\n",
    "                heapq.heappush(queue, [slots2[-index-1][1], slots2[-index-1][0], index])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        slots1.sort(key=lambda v:v[1])\n",
    "        slots2.sort(key=lambda v: v[1])\n",
    "        n=len(slots1)\n",
    "        m=len(slots2)\n",
    "        left=0\n",
    "        right=0\n",
    "        c=[]\n",
    "        while(left<n and right<m):\n",
    "                a=max(slots1[left][0],slots2[right][0])\n",
    "                b=min(slots1[left][1],slots2[right][1])\n",
    "                c.append([a,b])\n",
    "                if(slots1[left][1]>=slots2[right][1]):\n",
    "                        right+=1\n",
    "                else:\n",
    "                        left+=1\n",
    "        for i in range(len(c)):\n",
    "                if(c[i][0]+duration<=c[i][1]):\n",
    "                        return [c[i][0],c[i][0]+duration]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:\n",
    "        arr = [(s, e) for s, e in slots1 if (e - s) >= duration]\n",
    "        brr = [(s, e) for s, e in slots2 if (e - s) >= duration]\n",
    "        arr.sort() \n",
    "        arr = [(float('-inf'), float('-inf'))] + arr + [(float('inf'), float('inf'))] \n",
    "        brr.sort() \n",
    "        def upper_bound(x):\n",
    "            l, r = -1, len(arr)\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if arr[mid][0] <= x:\n",
    "                    l = mid \n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return l \n",
    "        #print(arr)\n",
    "        #print(brr) \n",
    "        for s, e in brr:\n",
    "            idx1 = upper_bound(s)\n",
    "            idx2 = upper_bound(e) \n",
    "            #print(idx1, idx2) \n",
    "            for i in range(idx1, idx2+1):\n",
    "                if arr[i][0] <= s < arr[i][1] and e >= arr[i][1] and arr[i][1] - s >= duration:\n",
    "                    return [s, s+duration] \n",
    "                if s <= arr[i][0] and e >= arr[i][1]:\n",
    "                    return [arr[i][0], arr[i][0] + duration]\n",
    "                if s <= arr[i][0] and arr[i][0] <= e < arr[i][1] and e - arr[i][0] >= duration:\n",
    "                    return [arr[i][0], arr[i][0] + duration]\n",
    "                if arr[i][0] < s and e < arr[i][1]:\n",
    "                    return [s, s+duration] \n",
    "        return [] "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
